package oj;

public class LC70 {
    public int climbStairs(int n) {
        //动态规划 f(x)=f(x-1)+f(x-2)
        int p=0;
        int q=0;
        int r=1;
        for(int i=1;i<=n;i++){
            p=q;
            q=r;
            r=p+q;
        }
        return r;
    }
//动态规划 一维数组
//    public int climbStairs(int n) {
//        int[] dp=new int[n+2];
//        dp[0]=0;
//        dp[1]=1;
//        for(int i=2;i<dp.length;i++){
//            dp[i]=dp[i-1]+dp[i-2];
//        }
//        return dp[n+1];
//    }
}
